import java.util.Stack;

/*
题目描述：输入两个整数序列，一个表示栈的压入序列，另一个表示栈的弹出序列，验证合法性
方法：用栈模拟
 */
public class E31 {
    public static void main(String[] args) {
        int[] pushA = {1,2,3,4,5};
        int[] popA = {4,5,3,2,1};

        boolean res = IsPopOrder(pushA, popA);

        System.out.println(res);
    }

    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA == null && popA == null || pushA.length == 0 && popA.length == 0){
            return true;
        }
        int len = pushA.length;
        int index1 = 0, index2 = 0;
        Stack<Integer> stack = new Stack<>();
        while(index2 != len){   //index2 == len是终点
            //单个进栈出栈方式无需模拟，直接跳过
            while(index1 < len && pushA[index1] == popA[index2]){
                index1 ++;
                index2 ++;
            }
            //
            while(index1 < len && pushA[index1] != popA[index2]){
                stack.push(pushA[index1++]);
            }
            //分为两种情况，一种是index1走到头儿了，
            //另一种是pushA[index1] == popA[index2], 此时需要弹栈进行验证
            if(index1 == len){
                while(index2 != len && stack.pop() == popA[index2]){
                    index2++;
                }
                if(index2 != len){
                    return false;
                }
                else{
                    return true;
                }
            }
            else{
                while(index1 < len && pushA[index1] == popA[index2]){
                    index1 ++;
                    index2 ++;
                }
                if(index1 < len && pushA[index1] != popA[index2]){
                    continue;
                }
                while(index2 != len && stack.pop() == popA[index2]){
                    index2++;
                }
                if(index2 != len){
                    return false;
                }
                else{
                    return true;
                }
            }
        }
        return true;
    }
}
